package year2023.recursion;


/*
9.1上楼梯
有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。
请实现一个方法，计算小孩有多少种上楼的方式。
为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。
保证n小于等于100000。

*/

public class Code01_ClimbTheStairs {

    static final int mod = 1000000007;

    public static void main(String[] args) {
        System.out.println(recursion1(5));
        System.out.println(recursion2(5));
    }

    //递归  O(3^n)
    public static long recursion1(int n){
        if (n < 0) return 0;
        if (n == 0 || n == 1) return 1;
        if (n == 2) return 2;
        return recursion1(n - 1) % mod + recursion1(n - 2) % mod + recursion1(n - 3) % mod;
    }

    //迭代(正推)
    public static int recursion2(int n){
        if (n < 0) return 0;
        if (n == 0 || n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;

        int x1 = 1;
        int x2 = 2;
        int x3 = 4;
        for (int i = 4; i <= n; i++){
            int x_1 = x1;
            x1 = x2 % mod;
            x2 = x3 % mod;
            x3 = ((x1 + x2) % mod + x_1) % mod;
        }
        return x3;
    }

}
